package leetcode.templates.graphs;

import java.util.LinkedList;
import java.util.Queue;

//[785. 判断二分图](https://leetcode.cn/problems/is-graph-bipartite/)
public class Ring1 {

	// 多路无向图环
	public boolean isBipartite(int[][] graph) {
		int n = 101;
		int[] cnts = new int[n];
		for (int u = 0; u < graph.length; u++) {
			if (cnts[u] == 0) {
				Queue<Integer> queue = new LinkedList<>();
				queue.add(u);
				int cnt = 1;
				while (!queue.isEmpty()) {
					int size = queue.size();
					while (size > 0) {
						int cur = queue.poll();
						cnts[cur] = cnt;
						int[] g = graph[cur];
						for (int i = 0; i < g.length; i++) {
							int v = g[i];
							if (cnts[v] != 0) {
								if (((cnt - cnts[v]) & 1) == 0) {
									return false;
								}
							} else {
								queue.add(g[i]);
							}
						}
						size--;
					}
					cnt++;
				}
			}
		}
		return true;
	}
}
